#include<iostream>
using namespace std;
typedef struct BSTNode
{
	int val;
	struct BSTNode* left;
	struct BSTNode* right;
}BSTNode;
void create_BST(BSTNode** root, int a[], int& x, int n)
{
	if (*root == nullptr)
	{
		*root = new BSTNode;
		(*root)->val = a[x];
		(*root)->left = nullptr;
		(*root)->right = nullptr;
		x++;
	}
	while (x < n)
	{
		BSTNode* r = *root;
		int m = a[x];
		while (1)
		{
			if (m > r->val && r->right == nullptr)
			{
				r->right = new BSTNode;
				r->right->val = m;
				r->right->left = nullptr;
				r->right->right = nullptr;
				break;
			}
			else if (m < r->val && r->left == nullptr)
			{
				r->left = new BSTNode;
				r->left->val = m;
				r->left->left = nullptr;
				r->left->right = nullptr;
				break;
			}
			else
			{
				if (m > r->val)
					r = r->right;
				else
					r = r->left;

			}
		}
		x++;
	}
	
}
void pre_BST(BSTNode* root)
{
	if (root == nullptr)
	{
		cout << "# ";
		return;
	}
	else
	{
		cout << root->val << ' ';
		pre_BST(root->left);
		pre_BST(root->right);
	}
}
void delet_val(BSTNode* root, int val)
{
	BSTNode* r = root;
	while (r->val!=val)
	{
		if (r->val > val)
			r = r->left;
		else
			r = r->right;
	}
	if (r->left == nullptr && r->right != nullptr)
	{
		r->val = r->right->val;
		free(r->right);
		r->right = nullptr;
	}
	else if (r->right == nullptr && r->left != nullptr)
	{
		r->val = r->left->val;
		free(r->left);
		r->left = nullptr;
	}
	else if(r->left==r->right)
	{
		BSTNode* rn = root;
		while (rn->right != r&&rn->left!=r)
		{
			if (rn->val > val)
				rn = rn->left;
			else
				rn = rn->right;
		}
		free(r);
		rn->left = nullptr;
		rn->right = nullptr;
	}
	else
	{
		BSTNode* rn = r->left;
		while (rn->left || rn->right)
		{
			if (rn->right != nullptr)
				rn = rn->right;
		}
		BSTNode* rn2 = r;

		while (rn2->right != rn && rn2->left != rn)
		{
			if (rn2->val > val)
				rn2 = rn2->left;
			else
				rn2 = rn2->right;
		}
		r->val = rn->val;
		if (rn2->left == rn)
			rn2->left = nullptr;
		else
			rn2->right = nullptr;
		free(rn);
		
	}
}
void mid_BST(BSTNode* root)
{
	if (root == nullptr)
	{
		return;
	}
	else
	{
		mid_BST(root->left);
		cout << root->val << ' ';
		mid_BST(root->right);
	}
}
int levelfind(BSTNode* root, int val, int h)
{
	if (root == nullptr)
		return 0;
	if (root->val == val)
		return h;
	if (val > root->val)
	{
		int h2=levelfind(root->right, val,h + 1);
		if (h2)
			return h2;
	}
	else
	{
		int h3 = levelfind(root->left,val, h + 1);
		if (h3)
			return h3;
	}
	return 0;
}
int main()
{
	int a[100] = { 0 };
	int n = 0;
	while (1)
	{
		int x;
		cin >> x;
		if (x == 0)
			break;
		a[n++] = x;
	}
	BSTNode* root = 0;
	int x = 0;
	create_BST(&root, a, x, n);
	pre_BST(root);
	cout << endl;
	int val;
	cin >> val;
	delet_val(root, val);
	mid_BST(root);
	cout << endl;
	int val2;
	cin >> val2;
	int l = levelfind(root, val2,1);
	cout << l;
}